本篇同步發布於Blog: [解題] LeetCode - 821 Shortest Distance to a Character

平台：

LeetCode

題號：

821 - Shortest Distance to a Character

題目連結：

https://leetcode.com/problems/shortest-distance-to-a-character/

題目說明：

        輸入1個字串S 與 1個字元C，這字串S至少出現1個C字元，求S的每個字元到C字元的最短距離。

        比如範例輸入的 S = "loveleetcode", C = 'e'，第1個字元l距離e的最短距離為3、第2個字元o距離e的最短距離為2、第3個字元v距離e的最短距離為1、第4個字元e距離e的最短距離為0，完整的答案為[3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]。

解題方法：

   　一開始從左邊掃描目前有C字元的位置，並與之後每個位置計算距離，如果目前都沒遇到C字元，則當下那位置會標記為一個無限大的值。

再從右邊掃描，一樣紀目前有C字元的位置，並與之後每個位置計算距離，並比對前面從左邊掃描的距離誰是最小的，則為答案。

比如 S = "loveleetcode", C = 'e'，初始化一個陣列ans[12]

從左邊掃描，ans的變化為 [inf, inf, inf, 0, 1, 0, 0, 1, 2, 3, 4, 0]

再換右邊掃描，ans的變化為[min(inf, 3), min(inf, 2), min(inf, 1), 0, min(1, 1), 0, 0, min(1, 4), min(2, 3), min(3, 2) , min(4, 1), 0] = [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

難度為Easy

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
#define MAXINT 99999
using namespace std;

class Solution {
public:
    vector<int> shortestToChar(string S, char C) {
        vector<int> ans(S.length());
        
        int prev = -MAXINT;
        for(int i = 0 ; i < S.length();++i){
            if(S[i] == C){
                prev = i;
            }
            
            ans[i] = i - prev;
        }
        
        prev = MAXINT;
        for(int i = S.length() - 1 ; i >= 0;--i){
            if(S[i] == C){
                prev = i;
            }
            
            ans[i] = min(ans[i], prev - i);
        }
        
        return ans;
    }
};

int main()
{
    Solution s;
	vector<int> ans = s.shortestToChar("loveleetcode", 'e');
	for(int num : ans){
		cout << num << endl;
	}

    return 0;
}

using System;

namespace LeetCode821
{
	public class Solution {
		private const int MAXINT = 99999;
		public int[] ShortestToChar(string S, char C) {
			int[] ans = new int[S.Length];
			
			int prev = -MAXINT;
			for(int i = 0 ; i < S.Length;++i){
				if(S[i] == C){
					prev = i;
				}
				
				ans[i] = i - prev;
			}
			
			prev = MAXINT;
			for(int i = S.Length - 1 ; i >= 0;--i){
				if(S[i] == C){
					prev = i;
				}
				
				ans[i] = Math.Min(ans[i], prev - i);
			}
			
			return ans;
		}
	}
	
	public class Program
	{
		public static void Main()
		{
			Solution sol = new Solution();
			int[] ans = sol.ShortestToChar("loveleetcode" , 'e');
			foreach(int num in ans)
			{
				Console.WriteLine(num);
			}

			Console.Read();
		}
	}
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/800-899/821.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/800-899/821.cs